#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<int>weight(n + 1), values(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> weight[i] >> values[i];
    vector<vector<int>>dp(n + 1, vector<int>(m + 1, -1));
    for (int i = 0; i <= n; i++)dp[i][0] = 0;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j]=max(dp[i-1][j],j-weight[i]>=0&&dp[i-1][j-weight[i]]!=-1?dp[i-1][j-weight[i]]+values[i]:-1);
            ans = max(ans, dp[i][j]);
        }
    }
    cout << ans<<endl<<(dp[n][m]==-1?0:dp[n][m]);
    return 0;
}
//空间优化
int main() {
    int n, m;
    cin >> n >> m;
    vector<int>weight(n + 1), values(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> weight[i] >> values[i];
    vector<int>dp(m + 1, -1);
    int ans = 0;
    dp[0]=0;
    for (int i = 1; i <= n; i++) {
        for (int j = m; j-weight[i]>=0; j--) {
            dp[j]=max(dp[j],dp[j-weight[i]]!=-1?dp[j-weight[i]]+values[i]:-1);
            ans = max(ans, dp[j]);
        }
    }
    cout << ans<<endl<<(dp[m]==-1?0:dp[m]);
    return 0;
}